package problem127;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

//127.单词接龙
//https://leetcode.cn/problems/word-ladder/

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        HashSet<String> vis = new HashSet<>();
        HashSet<String> hash = new HashSet<>();
        for(String s : wordList) hash.add(s);
        vis.add(beginWord);
        Queue<String> queue = new LinkedList<>();
        queue.add(beginWord);
        int step = 1;
        if(!hash.contains(endWord)) return 0;
        while(!queue.isEmpty()) {
            int size = queue.size();
            step++;
            System.out.println(queue + " " + step);
            while(size-- > 0) {
                String s = queue.poll();
                for(int i = 0; i<s.length(); i++) {
                    char[] t = s.toCharArray();
                    for(char c = 'a'; c <= 'z'; c++) {
                        t[i] = c;
                        String next = new String(t);
                        if(next.equals(endWord)) return step;
                        if(!vis.contains(next) && hash.contains(next)) {
                            queue.add(next);
                            vis.add(next);
                        }
                    }
                }
            }
        }
        return 0;
    }
}